package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 95. 不同的二叉搜索树 II
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/15 9:09
 */
public class GenerateTrees {
    public List<TreeNode> generateTrees(int n) {

        List<List<TreeNode>> all = new ArrayList<>(n);

        List<TreeNode> list = new ArrayList<>();
        if (n != 0) {

            TreeNode t = new TreeNode(1);
            list.add(t);
            all.add(list);

            for (int i = 2; i <= n; i++) {
                list = new ArrayList<>();
                List<TreeNode> treeNodes = all.get(i - 2);
                List<TreeNode> treeNodes2;
                for (TreeNode treeNode : treeNodes) {
                    t = new TreeNode(i);
                    t.left = treeNode;
                    list.add(t);
                    t = new TreeNode(i);
                    t.right = treeNode;
                    list.add(t);
                }

                for (int j = 1; j < i - 1; j++) {
                    treeNodes = all.get(j - 1);
                    treeNodes2 = all.get(i - j - 2);
                    for (TreeNode treeNode : treeNodes) {
                        for (TreeNode treeNode2 : treeNodes2) {
                            t = new TreeNode(i);
                            t.left = treeNode;
                            t.right = treeNode2;
                            list.add(t);
                        }
                    }
                }
                all.add(list);
            }
            list = all.get(n - 1);
            List<TreeNode> li = new ArrayList<>();
            for (TreeNode treeNode : list) {
                count = 0;
                li.add(cc(treeNode));
            }
            return li;

        }


        return list;
    }

    static int count;

    public TreeNode cc(TreeNode treeNode) {
        TreeNode t = null;
        if (treeNode != null) {
            TreeNode l = cc(treeNode.left);
            t = new TreeNode(++count);
            TreeNode r = cc(treeNode.right);
            t.left = l;
            t.right = r;
        }
        return t;
    }
}
